//
// Created by wdq on 2022/9/8.
//
#include <iostream>
#include <cstring>

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 100

template<typename ElemType>
struct SeqList {
    ElemType *data;
    int length;
    int capacity;

    /*!
     * 构造函数
     * @param capacity 初始化容量大小，不传默认为LIST_INIT_SIZE
     */
    explicit SeqList(int capacity = LIST_INIT_SIZE) {
        this->length = 0;
        this->capacity = capacity;
        this->data = new ElemType[capacity];
    }

    /*!
     * 析构函数
     */
    ~SeqList() {
        delete[]this->data;
    }

    /*!
     *
     * @param index 索引
     * @return 值
     */
    ElemType get(int index) {
        if (index < 0 || index >= this->length)
            throw std::out_of_range("the index is not legal!");
        return this->data[index];
    }

    /*!
     * 扩容函数
     * @param targetCapacity 目标容量
     */
    void expansion(int targetCapacity = LIST_INCREMENT) {
        this->capacity = targetCapacity;
        auto *newData = new ElemType[this->capacity];
        delete[]this->data;
        //将原来的数据拷贝到新的地址
        memcpy(newData, this->data, this->length * sizeof(ElemType));
        this->data = newData;
    }

    /*!
     *
     * @param index 索引
     * @param value 要设置的值
     */
    void set(int index, ElemType value) {
        if (index < 0 || index >= this->length)
            throw std::out_of_range("the index is not legal!");
        this->data[index] = value;
    }


    /*!
     * 运算符重载,并返回真正的值，不返回拷贝的值
     * @param index
     * @return
     */
    ElemType &operator[](int index) {
        if (index < 0 || index >= this->length)
            throw std::out_of_range("the index is not legal!");
        return this->data[index];
    }

    /*!
    * 将元素加到最后
    * @param value
    */
    virtual void push(ElemType value) {
        //判断容量是否够，不够就扩容，够就直接添加
        if (this->length < this->capacity) {
            this->data[this->length++] = value;
            return;
        }
        expansion(this->capacity + LIST_INCREMENT);
        this->data[length++] = value;
    }

    /*!
    * 删除最后一个元素
    * @return
    */
    virtual ElemType pop() {
        if (this->isEmpty()) {
            throw std::out_of_range("there is no element in list!");
        }
        return this->data[--this->length];
    }

    /*!
     * 找到元素的位置，没有就返回-1
     * @param value
     * @return index
     */
    int find(ElemType value) {
        for (int i = 0; i < this->length; i++) {
            if (this->get(i) == value) {
                return i;
            }
        }
        return -1;
    }

    /*!
     * 删除指定位置的元素
     * @param index
     */
    void deleteElement(int index) {
        for (int i = index; i < this->length - 1; i++) {
            this->data[i] = this->data[i + 1];
        }
        this->length--;

    }


    /*!
     * 向指定位置插入元素
     * @param index
     * @param value
     */
    void insert(int index, ElemType value) {
        for (int i = this->length; i > index; i--) {
            this->data[i] = this->data[i - 1];
        }
        this->data[index] = value;
        this->length++;

    }


    /*!
     * 打印函数
     */
    void print() {
        for (int i = 0; i < this->length; i++) {
            std::cout << this->get(i) << " ";
        }
        std::cout << std::endl;
    }

    /*!
     * 判断数组是否为空
     * @return
     */
    bool isEmpty() {
        return this->length == 0;
    }


};

template<typename ElemType>
struct Stack : public SeqList<ElemType> {
    int top;

    Stack() : SeqList<ElemType>() {
        this->top = 0;
    }


    void push(ElemType value) override {
        SeqList<ElemType>::push(value);
        this->top++;
    }

    ElemType pop() override {
        this->top--;
        return SeqList<ElemType>::pop();
    }

    ElemType peek() {
        return SeqList<ElemType>::get(top - 1);
    }


};

int main() {
    Stack<int> stack;
    for (auto i = 0; i <= 5; i++) {
        stack.push(i);
    }
    stack.print();
    std::cout << stack.peek() << std::endl;
    while (!stack.isEmpty()) {
        stack.print();
        std::cout << stack.pop() << " ";
    }
    return 0;
}